#ifndef SORT_DEMO_HPP
#define SORT_DEMO_HPP

#include <iostream>

namespace sort {

void test_print(int *arr, int len) {
  for (int i = 0; i < len; i++) {
    std::cout << " " << arr[i];
  }
  std::cout << std::endl;
}

/// 快速排序
void quick_sort(int *arr, int len) {

}

/// 插入排序
/// 移动次数很多
/// 有序序列在前，待排序序列在后，从无序序列拿出来放在有序序列里面的排序
/// 假设从小到大排序
void insert_sort(int *arr, int len) {
  for (int i = 0; i < len; i++) {
    for (int j = i + 1; j > 0; --j) {
      if (arr[j] < arr[j - 1]) {
        int tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
      }
    }
  }
}

/// 二分排序
/// 中间的值不变，位置改变
void _binary_sort(int *arr, int left, int right) {
  int mid = (right + left) / 2;
  if (mid == right || mid == left) {
    return;
  } 
  int len = right - left + 1;
  for (size_t i = left; i <= right; i++) {
    if (i < mid) {
      if (arr[i] > arr[mid]) {
        //局部交换
        int tmp = arr[i];
        int count = 0;
        while (count < mid - i) {
          arr[i + count] = arr[i + count + 1];
          ++count;
        }
        arr[i + count] = tmp;
        mid--;
        // test_print(arr, len);
      }
    } else if (i > mid) {
      if (arr[i] < arr[mid]) {
        //局部交换
        int tmp = arr[i];
        int count = 0;
        while (count < i - mid) {
          arr[i - count] = arr[i - count - 1];
          ++count;
        }
        arr[i - count] = tmp;
        mid++;
        // test_print(arr, len);
      }
    } else {
      // ==
    }
  }
  // test_print(arr, 10);
  // std::cout << "mid = " << mid << ", arr[mid] = " << arr[mid] << std::endl;
  // std::cout << "left = " << left << ", arr[left] = " << arr[left] << std::endl;
  // std::cout << "right = " << right << ", arr[right] = " << arr[right] << std::endl;
  _binary_sort(arr, left, mid - 1);
  _binary_sort(arr, mid + 1, right);
}
void binary_sort(int *arr, int len) { _binary_sort(arr, 0, len - 1); }

/// 冒泡排序
/// 排序的方式向泡泡所以得名
/// 相邻元素交互，以从小到大排序，一次遍历，最大元素交换到最后面
void bubbling_sort(int *arr, int len) {
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      if (arr[j] < arr[j + 1]) {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
}

} // namespace sort

#endif // SORT_DEMO_HPP